package org.example.queue;

public class MyPriorityQueue {
    //演示使用，不在考虑扩容部分代码
    private int[] array=new int[100];
    private int size=0;
    //添加新元素到优先队列中，然后通过 shiftUp 方法调整堆结构以确保堆性质。
    public void offer(int e){
        if (size>=array.length){
            throw new RuntimeException("优先队列已满");
        }
        array[size++]=e;
        shiftUp(size - 1);
    }
    //移除并返回堆顶元素（即最小值），将最后一个元素移到堆顶，然后通过 shiftDown 方法调整堆结构。
    public int poll(){
        if (size<=0){
            throw new RuntimeException("优先队列已空");
        }
        int oldValue=array[0];
        array[0]=array[--size];
        shiftDown(0);
        return oldValue;
    }
    //返回堆顶元素而不移除它。
    public int peek(){
        if (size<=0){
            throw new RuntimeException("优先队列已空");
        }
        return array[0];
    }
    //当插入新元素时，从插入位置向上调整堆，直到满足小根堆的性质。
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0 && array[child] < array[parent]) {
            swap(array, child, parent);
            child = parent;
            parent = (child - 1) / 2;
        }
    }
    //当移除堆顶元素后，从堆顶向下调整堆，确保堆的性质不被破坏。
    private void shiftDown(int parent) {
        int child = parent * 2 + 1; // left child
        int size = this.size;

        while (child < size) {
            // 如果右孩子存在，并且比左孩子更小，则指向右孩子
            if (child + 1 < size && array[child + 1] < array[child]) {
                child += 1;
            }
            // 如果父节点小于等于较小的孩子，调整结束
            if (array[parent] <= array[child]) {
                break;
            } else {
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
